package offer;

import java.util.Arrays;

/**
 * @Author Elephas
 * @Date 2022/1/28
 **/
@FunctionalInterface
public interface MaxProfit {
    int maxProfit(int[] prices);
}
class MaxProfitImpl1 implements MaxProfit{
    /**
     * 实现思路，动态规划，记 F(i,j) 为第 i 天买入，第j天卖出的利润，delta 为当天的价格增量
     * 则有 F(i,j) = F(i,j-1) + delta[j] , j > i
     *     F(i,j) = 0; j <= i
     * 用二维数组内存超过限制.gg
     * @param prices
     * @return
     */
    @Override
    public int maxProfit(int[] prices) {
        int[] delta = new int[prices.length];
        delta[0] = 0;
        for (int i = 1; i < delta.length; i++) {
            delta[i] = prices[i] - prices[i - 1];
        }
        int[][] dp = new int[prices.length][prices.length];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp.length; j++) {
                dp[i][j] = 0;
            }
        }
        for (int i = 0; i < dp.length; i++) {
            for (int j = i + 1; j < dp.length; j++) {
                dp[i][j] = dp[i][j-1] + delta[j];
            }
        }
        int maxProfit = 0;
        for (int i = 0; i < dp.length; i++) {
            for (int j = i + 1; j < dp.length; j++) {
                if(dp[i][j] > maxProfit){
                    maxProfit = dp[i][j];
                }
            }
        }
        return maxProfit;
    }
}

class MaxProfitImpl2 implements MaxProfit{

    @Override
    /**
     * 考虑优化动态规划
     */
    public int maxProfit(int[] prices) {
        int[] delta = new int[prices.length];
        // init the delta array
        delta[0] = 0;
        for (int i = 1; i < delta.length; i++) {
            delta[i] = prices[i] - prices[i - 1];
        }
        // compute the max profit according to the current profit.
        int maxProfit = 0,currentProfit = 0;
        for (int i : delta) {
            currentProfit += i;
            if(currentProfit > maxProfit){
                maxProfit = currentProfit;
            }
            if(currentProfit < 0){
                currentProfit = 0;
            }
        }
        return maxProfit;
    }
}
class MaxProfitImpl3 implements MaxProfit{

    @Override
    public int maxProfit(int[] prices) {
        int maxProfit = 0,currentProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            currentProfit += prices[i] - prices[i-1];
            if(currentProfit > maxProfit) {
                maxProfit = currentProfit;
            }
            if(currentProfit < 0)
                currentProfit = 0;
        }
        return maxProfit;
    }

}